/*
 * main.cpp
 *
 *  Created on: 16.10.2011
 *      Author: duke
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <math.h>
#include "mpi.h"
#include "dynamic_array.h"
#include "graph.h"
#include "edge.h"
#include "stackitem.h"

using namespace std;

#define 	USE_ADUV 	0
#define 	DEBUG 		0
#define 	TEST_DEPTH	4
#define 	TEST_EVERY	3
#define 	DIVIDE_HEIGHT	1
#define 	MAX_WORK_REQUESTS 	20

#define CHECK_MSG_AMOUNT  1000

#define MSG_WORK_REQUEST 1000
#define MSG_WORK_SENT    1001
#define MSG_WORK_NOWORK  1002
#define MSG_TOKEN        1003
#define MSG_FINISH       1004
#define MSG_WORK_SENT_END 1005
#define MSG_SEND_SOLUTION 1006
#define MSG_SOLUTION_NOT_FOUND 1007

#define ADUV_WHITE		0
#define ADUV_BLACK		1

int numofruns = 0;
int numofsolutions = 0;
long maxruns = 0;
int citac = 0;
int test_depth = TEST_DEPTH;
int test_every = TEST_EVERY;
int my_rank, num_of_processes;
int array_size;
char *char_buffer;
int *int_buffer;
int color = ADUV_WHITE;
int request_process = 1;
int request_sent = MAX_WORK_REQUESTS;
int nowork_responses;
bool work_done = false;
double t1, t2;
graph *g_input = NULL;
graph E, E1, E2;
graph A, B;
queue<stackitem> stack0;
queue<stackitem> stack1;
void runIterative(graph *, bool, int, int);
void jobs_done();
void state_expand();
bool stack_division(int);
void receive_work();
/*
 *
 */
int main(int argc, char** argv) {
	ifstream myfile;
	string line;
	int nodes, value;
	int j = 0;
	/* start up MPI */
	MPI_Init(&argc, &argv);
	/* find out process rank */
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
	/* find out number of processes */
	MPI_Comm_size(MPI_COMM_WORLD, &num_of_processes);
	printf("# of processes %d\n", num_of_processes);
	if (my_rank == 0) {
		myfile.open(argv[1], ios::in);
		if (myfile.is_open()) {
			getline(myfile, line);
			istringstream is(line);
			if ((is >> nodes).fail()) {
#if DEBUG == 1
				cout << "error!" << endl;
#endif
				return -1;
			}
#if DEBUG == 1
			cout << "# of nodes: " << nodes << endl;
#endif
			dynamic_array input(nodes, nodes);
			while (myfile.good()) {
				getline(myfile, line);
				if ((int) line.length() == nodes) {
					for (int i = 0; i < (int) line.length(); i++) {
						value = line[i] - '0';
						input[i][j] = value;
					}
					j++;
				}
			}
			myfile.close();
			cout << "---------------------------" << endl;
			//graph g1(input);
			g_input = new graph(input);
			maxruns = pow(2, g_input->numOfEdges());
			cout << "max # of runs: " << maxruns << endl;
			g_input->print();
			bool tfree = g_input->isTriangleFree(0);
			if (tfree)
				cout << "triangle-free? yes" << endl;
			else
				cout << "triangle-free? no" << endl;

			//runIterative(g_input, true, test_depth, test_every);
		} else {
			myfile.close();
		}
		t1 = MPI_Wtime(); /* pocatecni cas */
	}
	runIterative(g_input, true, test_depth, test_every);
	/* shut down MPI */
	MPI_Finalize();
	return 0;
}

// iterativni zpusob reseni pomoci stacku
void runIterative(graph *g, bool fast, int _test_depth, int _test_every) {
	int index = 0, flag, message, *array, position = 0, a, dest, finished = 0;
	bool work_sent = false;
	bool aduv_started = false;
	int token_recv_from;
	int token_recv;
	int token;
	MPI_Status status;
	nowork_responses = num_of_processes;
	if (my_rank == 0) {
		vector<edge> edges = g->getAllEdges();
		array_size = 2 + edges.size() * 3;
		stackitem si(-1, edges);

		char_buffer = new char[array_size * sizeof(int)];
		int_buffer = new int[array_size];
		// send to another processes # of edges
		for (dest = 1; dest < num_of_processes; dest++) {
			MPI_Send(&array_size, 1, MPI_INT, dest, 1, MPI_COMM_WORLD);
		}
		stack0.push(si);
		for (int i = 1; i < pow(2, num_of_processes - 1); i++) {
			si = stack0.front();
			stack0.pop();
			index = si.getIndex();
			si.setIndex(index + 1);
			si.setEdgeColor(index + 1, 0);
			stack0.push(si);
			si.setEdgeColor(index + 1, 1);
			stack0.push(si);
		}
		cout << stack0.size() << " states on the stack" << endl;
		// rozesilani prace
		for (dest = 1; dest < num_of_processes; dest++) {
			stack_division(dest);
		}
		work_sent = true;
	} else {
		// get # of edges from 0. process
		MPI_Recv(&array_size, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG,
				MPI_COMM_WORLD, &status);
		//cout << my_rank << " array size is " << array_size << endl;
		char_buffer = new char[array_size * sizeof(int)];
		int_buffer = new int[array_size];

		maxruns = pow(2, array_size / 3 - 2);
	}
	while (true) {
		citac++;
		if ((citac % CHECK_MSG_AMOUNT) == 0) {
			MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag,
					&status);
			if (flag) {
				switch (status.MPI_TAG) {
				case MSG_WORK_REQUEST: // zadost o praci, prijmout a dopovedet
					// zaslat rozdeleny zasobnik a nebo odmitnuti MSG_WORK_NOWORK
					// Jestliže procesor Pi pošle práci procesoru Pj, kde i>j,
					// pak Pi nastaví svou barvu na B.
					MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE,
							MSG_WORK_REQUEST, MPI_COMM_WORLD, &status);
					if (stack_division(status.MPI_SOURCE)) {
						if (aduv_started && my_rank > status.MPI_SOURCE) {
							//cout << my_rank << " ADUV black" << endl;
							color = ADUV_BLACK;
						}
					}
					break;
				case MSG_WORK_SENT: {
					case MSG_WORK_SENT_END: // prisel rozdeleny zasobnik, prijmout
					// deserializovat a spustit vypocet
					// get array with first tree
					receive_work();
					/*cout << "process " << my_rank
					 << " has got a job, stack size = " << stack0.size()
					 << endl;*/
					work_sent = true;
					nowork_responses = num_of_processes;
					if (my_rank == 0)
						aduv_started = false;
					//stackitem s1 = stack0.back();
					//s1.printArray();
					break;
				}
				case MSG_WORK_NOWORK: // odmitnuti zadosti o praci
					// zkusit jiny proces
					// a nebo se prepnout do pasivniho stavu a cekat na token
					MPI_Recv(NULL, 0, MPI_INT, MPI_ANY_SOURCE, MSG_WORK_NOWORK,
							MPI_COMM_WORLD, &status);
					work_sent = true;
					nowork_responses--;
					break;
				case MSG_TOKEN: //ukoncovaci token, prijmout a nasledne preposlat
					// - bily nebo cerny v zavislosti na stavu procesu
					if (my_rank == 0) {
						token_recv_from = num_of_processes - 1;
					} else {
						token_recv_from = my_rank - 1;
					}
					MPI_Recv(&token_recv, 1, MPI_INT, token_recv_from,
							MSG_TOKEN, MPI_COMM_WORLD, &status);
					/*cout << my_rank << " - " << token_recv
					 << " token received from " << token_recv_from
					 << endl;*/
					if (my_rank == 0) {
						if (!stack0.empty()) {
							aduv_started = false;
							work_sent = true;
							break;
						}
						if (token_recv == ADUV_BLACK) {
							// Pokud má pešek barvu B, P1 zahájí nové kolo vysláním barvy W procesoru P2.
							token = ADUV_WHITE;
							MPI_Send(&token, 1, MPI_INT, 1, MSG_TOKEN,
									MPI_COMM_WORLD);
							/*cout << my_rank << " sending WHITE token to P1"
							 << endl;*/
						} else {
							work_done = true;
							// Pokud P1 obdrží zpět peška barvy W, je možné výpočet ukončit
							//cout << "no job left!" << endl;
							E1.setEdges(E.getEdges(0));
							E2.setEdges(E.getEdges(1));
							for (int i = 1; i < num_of_processes; i++) {
								// posli ukonceni
								MPI_Send(NULL, 0, MPI_INT, i, MSG_FINISH,
										MPI_COMM_WORLD);
							}
							//cout << "0 work done" << endl;
							// konec programu
							//sleep(5);
							for (finished = 1; finished < num_of_processes;) {
								//if (finished != 3)
								//cout << "ffsdsf" << finished << endl;
								a++;
								if ((a % CHECK_MSG_AMOUNT) == 0) {
									MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG,
											MPI_COMM_WORLD, &flag, &status);
									if (flag) {
										//cout << "iprobe " << status.MPI_TAG
										//	<< endl;
										switch (status.MPI_TAG) {
										case MSG_SEND_SOLUTION: {
											cout << status.MPI_SOURCE << "recv"
													<< endl;
											// get array with first tree
											position = 0;
											MPI_Recv(char_buffer, (array_size
													* sizeof(int)), MPI_PACKED,
													MPI_ANY_SOURCE,
													MPI_ANY_TAG,
													MPI_COMM_WORLD, &status);
											cout << "Process "
													<< status.MPI_SOURCE << "/"
													<< num_of_processes
													<< " sent a solution..."
													<< endl;
											for (int i = 0; i < array_size; i++) {
												MPI_Unpack(char_buffer,
														(array_size
																* sizeof(int)),
														&position, &a, 1,
														MPI_INT, MPI_COMM_WORLD);
												int_buffer[i] = a;
											}
											stackitem
													s0(int_buffer, array_size);
											E1.setEdges(s0.getEdges(0,
													s0.getSize() + 1));
											E2.setEdges(s0.getEdges(1,
													s0.getSize() + 1));
											finished++;
											cout << "Process "
													<< status.MPI_SOURCE << "/"
													<< num_of_processes
													<< " quit..." << endl;
										}
											break;
										case MSG_SOLUTION_NOT_FOUND:
											cout << status.MPI_SOURCE << "recv"
													<< endl;
											MPI_Recv(NULL, 0, MPI_INT,
													MPI_ANY_SOURCE,
													MPI_ANY_TAG,
													MPI_COMM_WORLD, &status);
											finished++;
											cout << "Process "
													<< status.MPI_SOURCE << "/"
													<< num_of_processes
													<< " quit..." << endl;
											break;
										default:
											MPI_Recv(NULL, 0, MPI_INT,
													MPI_ANY_SOURCE,
													MPI_ANY_TAG,
													MPI_COMM_WORLD, &status);
											break;
										}
									}
								}
							}
							cout << endl << "BEST RESULTS: " << endl << "E1"
									<< endl;
							E1.print();
							cout << "E2" << endl;
							E2.print();
							jobs_done();
							return;
						}
					} else {
						// nejsem root
						// at jsem cerny nebo bily - poslu svuj token - tady nebo jinde
						// pokud jeste makam, tak to poslu az skoncim s praci
						// Jestliže Pi obdrží peška, pak má-li Pi barvu B, nastaví barvu
						// peška na B. Jakmile se Pi stane idle, pošle peška po kružnici procesoru Pi+1 a
						// nastaví svoji barvu na W.
						aduv_started = true;
						if (token_recv == ADUV_BLACK) {
							token_recv = ADUV_BLACK;
							if (color == ADUV_BLACK)
								color = ADUV_WHITE;
						} else {
							if (stack0.empty()) {
								token_recv = ADUV_WHITE;
							} else {
								token_recv = ADUV_BLACK;
							}
						}
						/*cout << my_rank << " - sending " << token_recv
						 << " token to " << (my_rank + 1)
						 % num_of_processes << endl;*/
						MPI_Send(&token_recv, 1, MPI_INT, (my_rank + 1)
								% num_of_processes, MSG_TOKEN, MPI_COMM_WORLD);
					}
					break;
				case MSG_FINISH: //konec vypoctu - proces 0 pomoci tokenu zjistil, ze jiz nikdo nema praci
					//a rozeslal zpravu ukoncujici vypocet
					//mam-li reseni, odeslu procesu 0
					//nasledne ukoncim spoji cinnost
					//jestlize se meri cas, nezapomen zavolat koncovou barieru MPI_Barrier (MPI_COMM_WORLD)
					if (my_rank == 0) {
						//cout << my_rank << " - work ended" << endl;
					} else {
						MPI_Recv(NULL, 0, MPI_INT, 0, MSG_FINISH,
								MPI_COMM_WORLD, &status);
						work_done = true;
						//cout << my_rank << " - work ended" << endl;
						if (numofsolutions) {
							position = 0;
							int_buffer = E.getArray();
							for (int i = 0; i < array_size; i++) {
								a = int_buffer[i];
								MPI_Pack(&a, 1, MPI_INT, char_buffer,
										(array_size * sizeof(int)), &position,
										MPI_COMM_WORLD);
							}
							MPI_Send(char_buffer, position, MPI_PACKED, 0,
									MSG_SEND_SOLUTION, MPI_COMM_WORLD);
							//cout << my_rank << " send" << endl;
						} else {
							MPI_Send(NULL, 0, MPI_INT, 0,
									MSG_SOLUTION_NOT_FOUND, MPI_COMM_WORLD);
						}
					}
					jobs_done();
					break;
				default:
					//printf("neznamy typ zpravy");
					break;
				}
			}
		}
		for (int w = 0; w < 50; w++) {
			if (work_sent && !stack0.empty())
				state_expand();
			else
				break;
		}
		// test, jestli je zasobnik prazdny
		if (work_sent && stack0.empty() && my_rank == 0 && !aduv_started) {
			//cout << "P0 jobs done, sending white token" << endl;
			aduv_started = true;
			MPI_Send(&color, 1, MPI_INT, 1, MSG_TOKEN, MPI_COMM_WORLD);
			//work_sent = false;
		}
		if (work_sent && stack0.empty() && nowork_responses > 0 && !work_done) {
			// zasobnik je prazdny, pozadam o praci
			if (my_rank == request_process)
				request_process++;
			if (request_process > num_of_processes - 1 && my_rank != 0)
				request_process = 0;
			if (request_process > num_of_processes - 1 && my_rank == 0)
				request_process = 1;
			//cout << my_rank << " zadam o praci " << request_process << endl;
			MPI_Send(NULL, 0, MPI_INT, request_process, MSG_WORK_REQUEST,
					MPI_COMM_WORLD);
			request_process++;
			//request_sent--;
			work_sent = false;
			//work_request = true;
		}
		///////////////////////////////////////////////////
	}
}

void jobs_done() {
	MPI_Barrier(MPI_COMM_WORLD);
	cout << "Process " << my_rank << ", # of solutions: " << numofsolutions
			<< "/" << numofruns << "/" << maxruns << endl;
	if (my_rank == 0) {
		t2 = MPI_Wtime(); /* koncovy cas */
		printf("Spotrebovany cas je %f.\n", t2 - t1);
	}
	MPI_Finalize();
	exit(0);
}

void state_expand() {
	int index, position, array_size, a;
	stackitem si = stack0.front();
	stack0.pop();
	index = si.getIndex();
	numofruns++;
	if (index == si.getSize()) {
		A.setEdges(si.getEdges(0, index + 1));
		B.setEdges(si.getEdges(1, index + 1));
		if (A.numOfEdges() == B.numOfEdges() || A.numOfEdges()
				== B.numOfEdges() - 1 || A.numOfEdges() - 1 == B.numOfEdges()) {
			if (A.numOfEdges() > E1.numOfEdges() && A.isTriangleFree(index)
					&& B.isTriangleFree(index)) {
				// nalezeno lepsi reseni
				E.setEdges(si);
				numofsolutions++;
			}
		}
#if DEBUG == 1
		si.print();
#endif
	} else {
		si.setIndex(index + 1);
		si.setEdgeColor(index, 0);
		if (index >= TEST_DEPTH) {//&& index % TEST_EVERY == 0) {
			A.setEdges(si.getEdges(0, index + 1));
			if (A.isTriangleFree(0))
				stack0.push(si);
		} else {
			stack0.push(si);
		}
		si.setEdgeColor(index, 1);
		if (index >= TEST_DEPTH) {//&& index % TEST_EVERY == 0) {
			B.setEdges(si.getEdges(1, index + 1));
			if (B.isTriangleFree(0))
				stack0.push(si);
		} else {
			stack0.push(si);
		}
	}
}

bool stack_division(int process_number) {
	int index, position, value, tag = MSG_WORK_SENT, stack_size;
	if (stack0.empty() && !work_done) {
		cout << my_rank << " kaslu na " << process_number << " stack.size="
				<< stack0.size() << endl;
		MPI_Send(NULL, 0, MPI_INT, process_number, MSG_WORK_NOWORK,
				MPI_COMM_WORLD);
		return false;
	}
	stackitem si = stack0.front();
	index = si.getIndex();
	stack_size = ((int) stack0.size() / 2);
	//stack_size = 1;
	if (index < si.getSize() - DIVIDE_HEIGHT && process_number
			< num_of_processes && stack_size >= 1) {
		for (int i = 0; i < stack_size; i++) {
			position = 0;
			//cout << process_number << " stack.size/2= " << stack_size << endl;
			if (i == stack_size - 1) {
				tag = MSG_WORK_SENT_END;
				//cout << "work sent to " << process_number << endl << flush;
			}
			si = stack0.front();
			stack0.pop();
			int_buffer = si.getArray();
			for (int j = 0; j < array_size; j++) {
				value = int_buffer[j];
				MPI_Pack(&value, 1, MPI_INT, char_buffer, (array_size
						* sizeof(int)), &position, MPI_COMM_WORLD);
			}
			MPI_Send(char_buffer, position, MPI_PACKED, process_number, tag,
					MPI_COMM_WORLD);
		}
		cout << my_rank << " = stack division for " << process_number
				<< ", index = " << index << ", division size = " << stack_size
				<< endl;
		return true;
		//cout << process_number << "work size " << position << endl;
	} else {
		MPI_Send(NULL, 0, MPI_INT, process_number, MSG_WORK_NOWORK,
				MPI_COMM_WORLD);
		return false;
	}
}

void receive_work() {
	int position, value;
	MPI_Status status;
	while (true) {
		position = 0;
		MPI_Recv(char_buffer, (array_size * sizeof(int)), MPI_PACKED,
				MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
		for (int i = 0; i < array_size; i++) {
			MPI_Unpack(char_buffer, (array_size * sizeof(int)), &position,
					&value, 1, MPI_INT, MPI_COMM_WORLD);
			int_buffer[i] = value;
		}
		//cout << "work received" << endl;
		stack0.push(stackitem(int_buffer, array_size));
		if (status.MPI_TAG == MSG_WORK_SENT_END) {
			//cout << "sent end received" << endl;
			break;
		}
		//cout << "while" << endl;
	}
}

